Гном сорт

Гном сорт (енгл. Gnome sort) или Глупи сорт (енгл. Stupid sort), представио га је 2000. године Хамид Сарбази-Азад и назвао га Глупи сорт.^[1] Касније га је додатно описао Дик Грун и назвао га Гном сорт^[2]. Гном сорт представља једноставан алгоритам за сортирање сличан алгоритму сортирање уметањем. Разлика је у томе што се елемент доводи на своје место низом премештања, слично сортирању са мехурима (енгл. Bubble sort). У суштини је прост алгоритам, без угњеждених петљи. Време извршавања је $O(n^{2})$ , али тежи $O(n)$ ако је низ иницијално скоро сортиран.^[3] У пракси алгоритам може да ради истом брзином као сортирање уметањем.

Алгоритам увек налази прву позицију на којој су два суседна елемента у погрешном редоследу и замени их. Затим искоришћава чињеницу да замена елемената може да произведе нов пар суседа у погрешном редоследу и то само непосредно пре или после замењених елемената. Алгоритам не претпоставља да ли су елементи после текуће позиције сортирани, па мора само да провери позицију пре текуће.

Сложеност

Структура података: низ
Временска сложеност најгорег случаја: $O(n^{2})$
Временска сложеност просечног случаја: $O(n^{2})$
Временска сложеност најбољег случаја: $O(n)$
Просторна сложеност најгорег случаја: $O(1)$

Опис алгоритма

Испод је дат псеудокод алгоритма

ПРОГРАМ гномСорт(a[])
    позиција := 1
    док је (позиција < дужинаНиза(a))
        ако (a[позиција] >= a[позиција-1])
            позиција := позиција + 1
        иначе
            размени a[позиција] и a[позиција-1]
            ако (позиција > 1)
                позиција := позиција - 1
            КРАЈ ако
        КРАЈ ако
    КРАЈ док је
КРАЈ ПРОГРАМ

Пример

Дат је несортиран низ а = [5, 3, 2, 4]. „Тренурна позиција“ је означена подебњаним цифрама. Ово су кораци које гном сорт алгоритам извршава:

Тренутни низ	Тренутна операција
[5, 3, 2, 4]	a[позиција] < a[позиција-1], размени:
[3, 5, 2, 4]	a[позиција] >= a[позиција-1], увећај позиција:
[3, 5, 2, 4]	a[позиција] < a[позиција-1], размени и позиција > 1, умањи позиција:
[3, 2, 5, 4]	a[позиција] < a[позиција-1], размени и позиција <= 1, увећај позиција:
[2, 3, 5, 4]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 5, 4]	a[позиција] < a[позиција-1], размени и позиција > 1, умањи позиција:
[2, 3, 4, 5]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 4, 5]	a[позиција] >= a[позиција-1], увећај позиција:
[2, 3, 4, 5]	позиција == дужинаНиза(a), КРАЈ.

C++ имплементација

Ово је генеричка имплементација која имитира шаблон стандардне C++ сорт функције. Ова функција прерађена тако да може да ради са C низовима, C++11 низовима, редовима, листама и векторима.

#include <algorithm>

template <typename BidirectionalIterator>
void gnomeSort(BidirectionalIterator first, BidirectionalIterator last)
{
    BidirectionalIterator i = first, j = first;

    ++j;

    while (j != last)
        if (*i <= *j)
        {
            ++i;
            ++j;
        }
        else
        {
            std::iter_swap(i, j);

            if (i != first)
            {
                --i;
                --j;
            }
        }
}

Референце

^ http://sina.sharif.edu/~azad/stupid-sort.PDF
^ Gnome Sort - The Simplest Sort Algorithm
^ Paul E. Black. „gnome sort”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Приступљено 20. 8. 2011.

Спољашње везе

Гном сорт

[1] ttp://sina.sharif.edu/~azad/stupid-sort.PDF

[2] Gnome Sort - The Simplest Sort Algorithm

[3] Paul E. Black. „gnome sort”. Dictionary of Algorithms and Data Structures. U.S. National Institute of Standards and Technology. Приступљено 20. 8. 2011.

[1]

[2]

[3]